package basic.courseLearn02.recursion;

import org.junit.Test;
import basic.utils.CommonUtil;

public class FindMaxNum  {
    // 递归求解数组内的最大值

    /**
     * 返回最大数
     * @param arr   原始数组
     * @param leftIndex     左下标
     * @param rightIndex    右下标
     * @return [leftIndex,rightIndex]中的最大数
     */
    public static int findMax(int[] arr, int leftIndex ,int rightIndex) {
        // 1.1 截止条件
        if (leftIndex == rightIndex){
            return arr[leftIndex];
        }
        // 1.2 选择中点
        int center = leftIndex + ((rightIndex- leftIndex)>>1);
        // 1.3 进行递归

        int leftMax = findMax(arr,leftIndex,center);
        int rightMax = findMax(arr,center+1,rightIndex);
        return Math.max(
                leftMax,
                rightMax
        );
    }

    @Test
    public void test(){
//        int[] a = new int[]{1,7,2,4,8,4,2,3,5,2,8,5};
//        System.out.println(findMax(a,0,a.length-1));
        executeCheckAlgorithm(10000, 1000,1000);
    }

    public int rightAlgorithm(int[] arr){
        int max=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
        }
        return max;
    }

    public void executeCheckAlgorithm(int loopNum, int size, int limit){
        boolean right =true;
        int[] arr;
        for (int i = 0; i < loopNum; i++) {
//        1.生成数组result_a
            arr= CommonUtil.generateArrays(size,limit);

//        2.对数组a使用方式1求最大值
            int max1= rightAlgorithm(arr);

//        3.对数组a使用方式2求最大值
            int max2= findMax(arr,0,arr.length-1);

//        4.核实比对两数组
            if (max1!=max2){
                System.out.println("oh my god");
                right=false;
                break;
            }
        }
        if (right){
            System.out.println("very good");
        }
    }



}
